package dynamic_planning.chorus.java;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class Chorus {
    public static void main(String[] args) throws FileNotFoundException {
        System.setIn(new FileInputStream("in.txt"));

        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int n = sc.nextInt();
            int[] arr = new int[n];
            for (int i = 0; i < n; i++) {
                arr[i] = sc.nextInt();
            }

            int[] left = new int[n]; //存储每个数左边小于其的数的个数
            int[] right = new int[n];//存储每个数右边小于其的数的个数
            left[0] = arr[0];
            right[n - 1] = arr[n - 1];
            int num[] = new int[n];//记录以 i 为终点的从左向右和从右向走的子序列元素个数
            int index = 1;//记录当前子序列的长度
            for (int i = 1; i < n; i++) {
                if (arr[i] > left[index - 1]) {
                    //直接放在尾部
                    num[i] = index;//i 左侧元素个数
                    left[index++] = arr[i];//更新递增序列
                }
                else {
                    //找到当前元素应该放在的位置
                    int low = 0, high = index - 1;
                    while (low < high) {
                        int mid = (low + high) / 2;
                        if (left[mid] < arr[i]) low = mid + 1;
                        else high = mid;
                    }
                    //将所属位置替换为当前元素
                    left[low] = arr[i];
                    num[i] = low;//当前位置 i 的左侧元素个数
                }
            }
            index = 1;
            for (int i = n - 2; i >= 0; i--) {
                if (arr[i] > right[index - 1]) {
                    num[i] += index;
                    right[index++] = arr[i];
                }
                else {
                    int low = 0, high = index - 1;
                    while (low < high) {
                        int mid = (high + low) / 2;
                        if (right[mid] < arr[i]) low = mid + 1;
                        else high = mid;
                    }
                    right[low] = arr[i];
                    num[i] += low;
                }
            }
            int max = 1;
            for (int number : num)
                max = Math.max(max, number);
            // max+1 为最大的 k
            System.out.println(n - max);
        }
    }
}